class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int check[9];
    void dfs(vector<int> &nums)
    {
        if (path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            // // 方法一 ： 只关心不合法分支
            // if(check[i] == true || (i!=0 && nums[i]==nums[i-1] && check[i-1]==false))
            //     continue;
            // path.push_back(nums[i]);
            // check[i] = true;
            // dfs(nums);
            // check[i] = false;
            // path.pop_back();
            // 方法二 ： 只关心合法分支
            if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        dfs(nums);
        return ret;
    }
};
class Solution
{
public:
    vector<string> ret;
    string path;
    string arr[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void dfs(const string &digits, int pos)
    {
        if (pos == digits.size())
        {
            ret.push_back(path);
            return;
        }
        // pos表示digits第几个字符，“2345”。减去字符0，得到arr数组对应下标2,3,4,5
        // 范围for就遍历arr数组对应下标的字符串
        for (auto ch : arr[digits[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)
            return ret;
        dfs(digits, 0);
        return ret;
    }
};
class Solution
{
public:
    vector<string> ret;
    string path;
    int left = 0;
    int right = 0;
    int m = 0;
    void dfs()
    {
        // if(right == m)
        if (path.size() == 2 * m)
        {
            ret.push_back(path);
            return;
        }
        // 左括号数量要小于给的n，才能插入左括号
        if (left < m)
        {
            path.push_back('(');
            ++left;
            dfs();
            path.pop_back();
            --left;
        }
        // 右括号的数量要小于左括号的数量，才能插入右括号
        if (right < left)
        {
            path.push_back(')');
            ++right;
            dfs();
            path.pop_back();
            --right;
        }
    }
    vector<string> generateParenthesis(int n)
    {
        // 有效括号
        // 1、左括号总数量 == 右括号总数量 --->>> ()()()
        // 2、【从开头的】任意一个子串的，左括号数量 >= 右括号数量 --->>> ( ( () () ) () )
        m = n;
        dfs();
        return ret;
    }
};